package com.lfg.leetcode.leetcode500;


import com.alibaba.fastjson.JSON;

public class No913minFallingPathSum {
    public static void main(String[] args) {
        int ret2 = minFallingPathSum(new int[][]{{2, 1, 3}, {6, 5, 4}, {7, 8, 9}});
        System.out.println(JSON.toJSONString(ret2));
    }

    public static int minFallingPathSum(int[][] matrix) {
        int ret = Integer.MAX_VALUE;
        int[][] dp = new int[matrix.length][matrix.length];
        System.arraycopy(matrix[0], 0, dp[0], 0, matrix[0].length);
        for (int row = 1; row < matrix.length; row++) {
            for (int column = 0; column < matrix[row].length; column++) {

                dp[row][column] = dp[row - 1][column] + matrix[row][column];

                if (column > 0) {
                    dp[row][column] = Math.min(dp[row][column], dp[row - 1][column - 1] + matrix[row][column]);
                }
                if (column < matrix[row].length - 1) {
                    dp[row][column] = Math.min(dp[row][column], dp[row - 1][column + 1] + matrix[row][column]);
                }

            }
        }
        for (int column = 0; column < matrix.length; column++) {
            ret = Math.min(ret, dp[matrix.length - 1][column]);
        }
        return ret;
    }
}



